package cn.njupt.countSort;

import cn.njupt.utils.Asserts;
import cn.njupt.utils.Integers;

import java.util.Arrays;

//给定一个整型数组，返回排序后的相邻两数的最大差值
public class BucketSort2 {
    public static int getMax(Integer[] arr){
        if(arr==null || arr.length<2)return 0;
        Arrays.sort(arr);
        int result=0;
        for (int i = 1; i <arr.length ; i++) {
            int max=arr[i]-arr[i-1];
            result=Math.max(max,result);
        }
        return result;
    }
    public static int separateMax(Integer[] arr){
        if(arr==null || arr.length<2)return 0;

        int max=arr[0];
        int min=arr[0];
        int len=arr.length;
        for (int i = 1; i < arr.length; i++) {
            max=Math.max(max,arr[i]);
            min=Math.min(min,arr[i]);
        }
        if(max==min)return 0;
        boolean[] flag=new boolean[arr.length+1];
        int[] minValue=new int[arr.length+1];
        int[] maxValue=new int[arr.length+1];
        for (int i = 0; i < arr.length; i++) {
            int index=index(arr[i],max,min,len);
           // System.out.println(index);
            minValue[index]=flag[index]?Math.min(minValue[index],arr[i]):arr[i];
            maxValue[index]=flag[index]?Math.max(maxValue[index],arr[i]):arr[i];
            flag[index]=true;
        }
        int preMax=maxValue[0];
        int result=Integer.MIN_VALUE;
        for (int i = 1; i < minValue.length; i++) {
            if(flag[i]){
                if(minValue[i]-preMax>result){
                    result=minValue[i]-preMax;
                }
                preMax=maxValue[i];
            }

        }
        return result;
    }

    //得到num对应的桶的编号
    public static int index(int num, int max,int min,int len){
        int index=(int)((num-min+0.0)/(max-min)*len);
        return index;
    }

    public static void main(String[] args) {
        for (int i = 0; i <1000; i++) {
            Integer[] arr=Integers.random(100000,-100000,100000);
            Asserts.test(getMax(arr)==separateMax(arr));
        }

    }




}
